package com.xz.sort.cmp;

import com.xz.sort.Sort;

import java.util.Arrays;

/**
 * @author XZ
 * @create 2021-12-09 20:11
 *
 */
public class ASelfMergeSort<T extends Comparable<T>> extends Sort<T> {
    private T[] leftArray;

    @Override
    protected void sort() {
        leftArray = (T[])new Comparable[array.length >> 1];
        sort(0, array.length);
    }

    /**
     * 采用的是递归
     * @param begin：开始的位置
     * @param end：结束位置+1
     *           排序的数组：[begin,end)
     *           数组长度：end-begin
     */
    private void sort(int begin, int end) {
        if (end-begin<2) return;
        int mid = (begin + end) >> 1;
        sort(begin, mid);
        sort(mid, end);

        merge(begin, mid, end);
    }

    private void merge(int begin, int mid, int end) {

        int li = 0;
        int le = mid - begin;
        int ai = begin;
        int re = end;
        int ri = mid;

        for (int i = 0; i < le; i++) {
            leftArray[i] = array[begin + i];
        }

        while (li < le) {
            if (ri < re && cmp(leftArray[li], array[ri]) > 0) {
                array[ai++] = array[ri++];//
            } else {
                array[ai++] = leftArray[li++];
            }
        }
    }

//    @Override
//    public String toString() {
//        return "ASelfMergeSort{" +
//                Arrays.toString(array) +
//                '}';
//    }
}
